BZOJ3594【SCOI2014】方伯伯的玉米田 <树状数组优化DP>

Problem

【SCOI2014】方伯伯的玉米田

Description

方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。
这排玉米一共有株，它们的高度参差不齐。
方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。
方伯伯可以选择一个区间，把这个区间的玉米全部拔高单位高度，他可以进行最多次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。
问能最多剩多少株玉米，来构成一排美丽的玉米。

Input

第行包含个整数，分别表示这排玉米的数目以及最多可进行多少次操作。
第行包含个整数，第个数表示这排玉米，从左到右第株玉米的高度。

Output

输出个整数，最多剩下的玉米数。

Sample Input

1
2

3 1
2 1 3

Sample Output

Hint

标签：DP 树状数组

Solution

首先，显然每次拔高时，不管从哪里开始拔，区间右边界总是肯定不会使答案变小。有此贪心后，考虑到第株时前面拔高次，那么第株一定也已拔高次。

令表示考虑前株，共拔高了次，最多可以剩下多少。那么有

对于值，将其坐标设为，那么到时，需要找的是坐标在范围内的最小值，可以二维树状数组维护。

注意时第二层循环要倒着循环，以排除后效性，由于二维树状数组的坐标范围不能到，可以把所有坐标的横纵值强行加。

Code

#include <bits/stdc++.h>
#define MAX_N 10000
#define MAX_A 5500
#define MAX_M 500
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, a[MAX_N+5], tr[MAX_M+5][MAX_A+5];
void modify(int p, int q, int c) {
    for (int i = p; i <= MAX_M+1; i += (i&-i))
        for (int j = q; j <= MAX_A; j += (j&-j))
            tr[i][j] = max(tr[i][j], c);
}
int query(int p, int q) {
    int ret = 0;
    for (int i = p; i; i -= (i&-i))
        for (int j = q; j; j -= (j&-j))
            ret = max(ret, tr[i][j]);
    return ret;
}
int main() {
    read(n), read(m);	int f, ans = 0;
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= n; i++) for (int j = m; ~j; j--)
        ans = max(ans, f = query(j+1, a[i]+j)+1), modify(j+1, a[i]+j, f);
    return printf("%d\n", ans), 0;
}